package com.keqing.algorithm.leetcode.simple.searchInsert;

/**
 * 35. 搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 你可以假设数组中无重复元素。
 * 示例 1:
 * 输入: [1,3,5,6], 5
 * 输出: 2
 * 示例 2:
 * 输入: [1,3,5,6], 2
 * 输出: 1
 * 示例 3:
 * 输入: [1,3,5,6], 7
 * 输出: 4
 * 示例 4:
 * 输入: [1,3,5,6], 0
 * 输出: 0
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-insert-position
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SearchInsert {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int nums1[] = {10, 30, 50, 60};
        int target1 = 20;
        int i1 = solution.searchInsert(nums1, target1);
        System.out.println(i1);//期望1
    }
}

//思路：其实，这道题分为两个部分，前半部分就是传统的二分查找。关键在于要找到要按顺序插入的位置。
class Solution {
    public int searchInsert(int[] nums, int target) {
        int startIndex = 0;
        int endIndex = nums.length - 1;
        //把中间索引提到循环之外
        int midIndex = 0;
        while(startIndex <= endIndex){
            midIndex = startIndex + (endIndex - startIndex)/2;
            if(target == nums[midIndex]){
                return midIndex;
            } else if(target < nums[midIndex]){
                endIndex = midIndex - 1;
            } else if(target > nums[midIndex]){
                startIndex = midIndex + 1;
            }
        }
        //程序运行到这里，我们要知道一下几个事实：
        //1.二分法没有命中目标值，所以此时的midIndex
        if(target < nums[midIndex]){
            return midIndex;
        } else if(target > nums[midIndex]){
            return midIndex + 1;
        }
        throw new IllegalStateException("这里我要不抛出个异常，就会报错！");
    }
}